1. Field of the Invention
This invention relates to a syndrome generator for detecting and correcting errors in Hamming code, and a method for generating the syndrome for Hamming code. More particularly, this invention relates to the circuit arrangement for a parity check matrix to be used in generating the syndrome for Hamming code, and a method for generating the same.
2. Description of the Prior Art
A recent development in data processing technology has made possible a high speed processing of huge amounts of information. In such information process, there is a possibility that the data to be processed contain an error or errors. Thus, it is necessary for the errors in the data to be detected and corrected before the data go through data processing operations. For this purpose, different codes are used in this field of technology which provide a function to detect and correct errors in the data. Among them is the code named Hamming code. The error-detection and correction in Hamming code is now briefly described.
The following linear simultaneous equation is considered: ##EQU1## where n&gt;m, x.sub.i .epsilon.{0, 1}, and product and addition should be performed following the rules of Boolean algebra.
The equation (1) can be expressed in matrix as follows: ##EQU2## where X=(x.sub.1, x.sub.2. . . x.sub.n) represents a row vector and T is a symbol representing transposition.
In the equation (1) or (2), if (n-m)x.sub.i s are independently selected, then the value of the remaining mx.sub.j s are uniquely determined. The (n-m)x.sub.i s are called information bits, while mx.sub.j s are designated check bits. When the above matrix H for parity check is expressed as follows, it is called a canonical parity check matrix: ##EQU3## Where m+k=n, and Im designates a unit matrix of m rows and m columns. In this case, the check bits comprise the first m bits (x.sub.1, x.sub.2. . . x.sub.m), and from the equation HX.sup.T =0 (mod. 2), ##EQU4## Thus, the check bits can be produced from information bits.
On the other hand, the following equation is considered in connection with the equation (3): ##EQU5## The code word X is divided into information bits x.sub.I and the check bits x.sub.C : EQU X=(x.sub.C x.sub.I).
Then, the code word X is generated as follows: EQU X=x.sub.I G (mod. 2) (6)
The matrix G is called a generating matrix.
Now, the following equation is considered. EQU S=HY.sup.T ( 7)
When S=O, then Y.epsilon.{X}, and if S.noteq.0, then Y {X}. Note that {X}represents a set of code words X, or a code. Thus, by checking the value of S, it can be determined whether an applied code word Y contains an error. S is called a syndrome. If an applied code word Y includes a single error pattern ##EQU6## its syndrome S is given as EQU S=H(x+e.sub.i).sup.T =He.sub.i.sup.T ( 8)
Note that the syndrome S is identical to the vector of the i-th column in the parity check matrix.
From the above discussion, it can be seen that if each column in the parity check matrix H is represented by a vector other than zero vector and is different from each other, it is possible, by means of the syndrome S, to detect an error location in the code word Y, as well as to correct the error bit. The code produced by the generating matrix G=[P.sup.T, I.sub.k ] corresponding to the matrix H=[I.sub.m, P], which satisfies the above conditions, is designated Hamming code. Hamming code is in common use in the field of information processing as the code for single error correction. In order to correct an error, the syndrome for a supplied data is first obtained, and a single error pattern corresponding to the obtained syndrome is then added to the supplied data.
Correction of the data stored in semiconductor memory devices is one application where Hamming code is used to advantage, and such application is now specifically described. In recent computers ranging from mainframe computers to minicomputers, the greater the capacity for the main or primary storage unit involved, the larger the number of faulty storage elements or memory cells in the primary storage unit. Now it has been a general practice to accommodate in the primary storage unit a code for detecting and correcting errors in the data stored therein. For this data correction purpose, the above described Hamming code is utilized. The organization of a conventionally used syndrome generator is now described.
For the convenience of simplicity, a Hamming (21, 5) code is considered which comprises 5 check bits and 16 information bits. With this code, the parity check matrix H is represented as follows, for example: ##EQU7## In the above check matrix H, the binary numbers are arranged in a progressively increasing order from the first column to the 21st column. It is assumed that the first row constitutes the least significant bit (LSB), and the fifth row the most significant bit (MSB). Then, if the 2.sup.i -th columns (where i=0-4) are taken out from the matrix H to form a matrix, the resultant matrix of five columns and five rows comprises a unit matrix. Hence, in the Hamming code X=(x.sub.1, x.sub.2 . . . x.sub.21) for the above stated parity check matrix H, the parity check bits x.sub.C are given by (x.sub.1, x.sub.2, x.sub.4, x.sub.8, x.sub.16) from the following equation which has been explained hereinabove. EQU S=HX.sup.T =(S.sub.0, SY.sub.1, SY.sub.2, SY.sub.3, SY.sub.4).sup.T =0
Where SY.sub.i (i=0-4) represents an element in the syndrome S and is expressed as follows. EQU SY.sub.0 =x.sub.1 .sym.x.sub.3 .sym.x.sub.5 .sym.x.sub.7 .sym.x.sub.9 .sym.x.sub.11 .sym.x.sub.13 .sym.x.sub.15 .sym.x.sub.17 .sym.x.sub.19 .sym.x.sub.21 ( 9) EQU SY.sub.1 =x.sub.2 .sym.x.sub.3 .sym.x.sub.6 .sym.x.sub.7 .sym.x.sub.10 .sym.x.sub.11 .sym.x.sub.14 .sym.x.sub.15 .sym.x.sub.18 .sym.x.sub.19( 10) EQU SY.sub.2 =x.sub.4 .sym.x.sub.5 .sym.x.sub.6 .sym.x.sub.7 .sym.x.sub.12 .sym.x.sub.13 .sym.x.sub.14 .sym.x.sub.15 .sym.x.sub.20 .sym.x.sub.21( 11) EQU SY.sub.3 =x.sub.8 .sym.x.sub.9 .sym.x.sub.10 .sym.x.sub.11 .sym.x.sub.12 .sym.x.sub.13 .sym.x.sub.14 .sym.x.sub.15 ( 12) EQU SY.sub.4 =x.sub.16 .sym.x.sub.17 .sym.x.sub.18 .sym.x.sub.19 .sym.x.sub.20 .sym.x.sub.21 ( 13)
It is pointed out here that the matrix H in the expression (8) is neither [P, I.sub.k ] nor [I.sub.k P.sup.T ] in the form. However, as for the matrix H for generating the Hamming code, any matrix may be employed as far as the vector in each column is non-zero and is different from column to column in the matrix and further the matrix is equivalent to H.sub.o =[PI.sub.k ]. Locations for the parity check bits may suitably be selected depending on the configuration of the parity check matrix.
In FIG. 1, there is illustrated the arrangement of a typical prior-art syndrome generator for generating a syndrome S in accordance with the matrix H given by the expression (8).
Referring to FIG. 1, the illustrated syndrome generator functions in accordance with the above mentioned equations (9)-(13) to provide a syndrome S, and includes a data selector 3' and an operational block 15. The data selector 3' operates in response to select signals S.sub.0 -S.sub.4 to select the desired data from the data in the memory cells 21-1 to 21-21 on a selected row in the cell array 1. The memory cells 21-1, 21-2, 21-4, 21-8 and 21-16 store parity check bit data, while the remaining memory cells store information bit data. The operational block 15 executes the addition of the modulus 2 on the output from the data selector 3', i.e., it performs an exclusive OR operation. Specifically, the data selector 3' comprises a plurality of switching devices 4.sub.11 -4.sub.215 (n-channel MOS transistors in the illustrated example) which are arranged in a matrix of 21 rows and 5 columns. The five columns of the switching devices 4.sub.11 -4.sub.215 are supplied with select signals S.sub.0, S.sub.1, S.sub.2, S.sub. 3 and S.sub.4, respectively, and the switching devices in each columns are driven into conduction when the select signal applied thereto is at an active or high level state. Each of the switching devices 4.sub.11 -4.sub.215, when rendered conductive, delivers either the data stored in a memory cell or the "0" data depending on whether it is connected with the memory cells in the array 1 or the ground. It is noted here that the switching devices are interconnected with the memory cells and the ground so as to satisfy the equations (9)-(13). Thus, the select signals S.sub.0 -S.sub.4 direct operational performance as represented by the elements SY.sub.0 -SY.sub.4 of the syndrome S, respectively. As the select signal S.sub.0 is brought into an active state, the switching devices in the associated column in the data selector 3' function to select the memory cells in the cell array necessary for the execution of the equation (9). Similarly, in response to an active select signal S.sub.1, the associated column of switching devices operates to select the memory cells out of the cell array 1 required for the execution of the equation (10). The same is the case with the other selected signals S.sub.2 -S.sub.4.
The operational block 15 includes a plurality of exclusive OR circuits 15-1 to 15-21 which are provided corresponding to the rows of switching devices in the data selector 3', and are coupled to one another in a cascade connection. With this arrangement, each of the exclusive OR circuits 15-1 to 15-21 is supplied both with the output from its associated row of the data selector 3' and with the output from a preceding exclusive OR circuit. Upon receipt of the two outputs, each exclusive OR circuit feeds an exclusively OR-ed output to the next exclusive OR circuit. In this manner of operation, the final exclusive OR circuit 15-21 provides the element SY.sub.i (i=0-4) of the syndrome S as its output.
The element SY.sub.i in syndrome S=HX.sup.T =(SY.sub.i) (i=0-4) is obtained by driving the select signal Si successively to the active "high" level.
Now, it is assumed that memory cells 21-1 to 21-21 on a selected row in the cell array 1 contain check bits x.sub.1, x.sub.2, x.sub.4, x.sub.8 and x.sub.16 as determined by the data in the information bits. When the data X=(x.sub.1. . . x.sub.21) are read out from memory cells on the selected row, followed by sequentially activating the select signals S.sub.0 -S.sub.4, individual element SY.sub.i of the syndrome S with respect to the data X is obtained. If the read out data in the information bits contain no error, then each element SY.sub.i of the syndrome S is zero (S=HX.sup.T =0). On the other hand, if only the information bit x.sub.i in the data x is in error, then the generated syndrome S is equal to the i-th column in the check matrix H. Since the column vector in the check matrix H differs from column to column, it is feasible to locate the erroneous information bit and also to correct the data error. For example, if S=HX.sup.T =(1, 0, 1, 0, 0).sup.T, it can be seen from the expression (8) that the information bit x.sub.5 is incorrect. Then, the correction of the data is carried out by inverting the information bit x.sub.5, i.e. by adding the error pattern ##STR1## vectorially to the read-out data.
As has been described, the prior-art syndrome generator is designed to produce a syndrome in accordance with the equations (9)-(13) using the check matrix represented by the expression (8) where l-digit binary numbers other than the binary number 0 are arranged in a progressively increasing or decreasing order. This type of prior-art syndrome generator possesses several distinct disadvantages. For example, the syndrome generation based on the equations (9)-(13) makes it necessary to provide one separate exclusive OR circuit for every selected memory cell (or every code bit storage cell) as shown in FIG. 1. Phrased differently, the exclusive OR circuit must be provided at the same pitch as one pitch A of a memory cell, wherein the term "pitch" refers to the frequency of occurence of the cells or circuit elements along the substrate. As the memory cell area reduces with an ever-growing storage capacity of the memory device, the pitch requirement for the exclusive OR circuit gets more severe, making it increasingly difficult for the exclusive OR circuit to be formed within the same pitch as that of the memory cell. This constitutes a great impeding factor against a highly integrated memory device.
As is well known to those skilled in the art, large-scale integrated circuits or LSIs are also used for error correction in the area of data processing. In such application, too, a larger code length gives rise to similar problems.
Another disadvantage of the conventional syndrome generator is that it includes a large number of transistor devices arranged in rows and columns with complicated interconnections among them.